package hot100;


/*
 * Author：江松
 * Date：2023/4/16 9:46
 *
 电话号码的字母组合：
 1，DFS
 2,BFS,队列存放字符串，类似于层序的操作
 每次取出一层中的所有串对其进行拼接操作
 */

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main17 {

    public List<String> letterCombinations(String digits) {
        List<String>res=new LinkedList<>();
        if(digits.length()==0)return res;
        Queue<String> queue=new LinkedList<>();
        String num[]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        queue.offer("");

        for(int i=0;i<digits.length();++i){
            int id=digits.charAt(i)-'0';
            String now=num[id];

            int qsize=queue.size();
            for(int k=0;k<qsize;++k){
                String t=queue.poll();
                for(int j=0;j<now.length();++j){
                    queue.offer(t+String.valueOf(now.charAt(j)));
                }
            }

        }
        return new LinkedList<>(queue);
    }
    /*
    List<String>res=new LinkedList<>();
    //boolean vis[]=new boolean[26];
    String num[]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public void dfs(int id,String digits,String cur){
        if(id==digits.length()){
            res.add(cur);
            return;
        }
        String now=num[digits.charAt(id)-'0'];
        for(int i=0;i<now.length();++i){
            dfs(id+1,digits,cur+String.valueOf(now.charAt(i)));
        }
    }

    public List<String> letterCombinations(String digits) {
        if(digits.length()==0)return res;
        dfs(0,digits,"");
        return res;
    }
    */
}
